package com.dushougudu;

import algorithm.BinaryTree;
import org.junit.Before;
import org.junit.Test;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

public class TreeSearch {

    TreeNode root;
    TreeNode node2;
    TreeNode node3;
    TreeNode node4;
    TreeNode node5;
    TreeNode node6;
    TreeNode node7;

    @Before
    public void init() {
        root = new TreeNode(5);
        node2 = new TreeNode(4);
        node3 = new TreeNode(6);
        node4 = new TreeNode(1);
        node5 = new TreeNode(2);
        node6 = new TreeNode(7);
        node7 = new TreeNode(8);

        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
    }

    @Test
    public void preOrder() {
        doPreOrder(root);
    }

    public void doPreOrder(TreeNode root) {
        if (root == null) return;
        System.out.println(root.value);

        doPreOrder(root.left);
        doPreOrder(root.right);

    }

    @Test
    public void iterativePreorder() {
        //5412678
        doterativePreorder(root);
    }

    @Test
    public void iterativeInorder() {
        //1425768
        doIterativeInOrder(root);
    }

    @Test
    public void iterativePostorder() {
        //1247865
        doIterativePostOrder(root);
    }

    public void doIterativePreorderCommon(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                node = stack.pop();
                System.out.println(node.value);
            } else {
                if (node.right != null) {
                    stack.push(node.right);
                }

                stack.push(node);
                stack.push(null);

                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
    }

    /**
     * 非递归实现二叉树的先序遍历
     */
    public void doterativePreorder(TreeNode node) {
        Stack<TreeNode> stack = new Stack<>();
        if (node != null) {
            stack.push(node);
            while (!stack.empty()) {
                node = stack.pop();
                // 先访问节点
                System.out.print(node.value);
                // 把右子结点压入栈
                if (node.right != null) {
                    stack.push(node.right);
                }
                // 把左子结点压入栈
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
    }

    /**
     * 非递归实现二叉树的中序遍历
     */
    public void doIterativeInOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || stack.size() > 0) {
            // 把当前节点的所有左侧子结点压入栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            // 访问节点，处理该节点的右子树
            if (stack.size() > 0) {
                node = stack.pop();
                System.out.print(node.value);
                node = node.right;
            }
        }
    }

    /**
     * 非递归实现二叉树后序遍历
     */
    public void doIterativePostOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        // 访问根节点时判断其右子树是够被访问过
        TreeNode preNode = null;
        while (node != null || stack.size() > 0) {
            // 把当前节点的左侧节点全部入栈
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (stack.size() > 0) {
                TreeNode temp = stack.peek().right;
                // 一个根节点被访问的前提是：无右子树或右子树已被访问过
                if (temp == null || temp == preNode) {
                    node = stack.pop();
                    System.out.print(node.value);
                    preNode = node;// 记录刚被访问过的节点
                    node = null;
                } else {
                    // 处理右子树
                    node = temp;
                }
            }
        }
    }

    @Test
    public void bfs() {
        //5461278
        doBfs(root);
    }

    public void doBfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedBlockingDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.value);
            if (node.left != null) {
                queue.add(node.left);
            }

            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    @Test
    public void bfsForEach() {
        //5461278
        doBfsForEach(root);
    }

    public void doBfsForEach(TreeNode root) {
        Queue<TreeNode> queue = new LinkedBlockingDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.value);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }

}
